//【案例开放056】1022上机编程[实验室预约系统设计]学习交流
//日期：2021-10-29 16:19浏览：16198回复：532026-10-29
//失效最近编辑时间：2021-10-29 16:19
// 1.   题目
//今天学习1022专业级第二题。题目：
//请设计一个实验室预约系统
// BookingSystem，每个实验室可以添加开放时段用于预约，且预约时段必须在开放时段内，已被预约的时段不可再预约。实现以下功能：
// addLab(int labId, int startTime, int endTime)：增加编号为 labId
// 的实验室，并开放时段（左闭右开）。 ·
//若系统中不存在该实验室，则将该实验室添加到系统中，并设置开放时段为
//[startTime,endTime)，返回 true。 ·     若系统中已存在该实验室： o  如果时段
// [startTime,endTime) 与该实验室已有开放时段存在重叠，则不做操作并返回 false；
// o  否则，将该实验室新增开放时段 [startTime,endTime) ，并返回 true。
// bookTime(int recordId, int fromTime, int toTime)- 预约 [fromTime,toTime)
// 时段的实验室。 ·
//若存在一个或多个该时段的实验室可被预约，则预约其中最早添加到系统的实验室，并占用该实验室的
//[fromTime,toTime) 时段，最后返回被预约的实验室编号。 ·
//若该时段没有可用的实验室，则返回 -1； · 注意：系统保证为每次预约分配全局唯一的
// recordId 。 cancelBooking(int recordId) - 取消系统中编号为 recordId 的预约。
//·     若系统中存在编号为 recordId
//的预约且未被取消，则取消预约并释放其预约所占用时段，返回 true； ·
//否则不做任何操作，返回 false。 示例 1： 输入：
//["BookingSystem","addLab","addLab","bookTime","bookTime","cancelBooking"]
//[[],[3,4,19],[5,2,3],[2,12,15],[3,12,13],[2]]
//输出：[null,true,true,3,-1,true]
//解释：
// BookingSystem obj = BookingSystem(); // 返回 null 表示无输出
// obj.addLab(3,4,19); // 添加实验室成功，返回 true
// obj.addLab(5,2,3); // 添加实验室成功，返回 true
// obj.bookTime(2,12,15); // 此时段可被预约的实验室编号为 3，返回 3
// obj.bookTime(3,12,13); // 此时段没有可预约的实验室，返回 -1
// obj.cancelBooking(2); // 取消编号为 2 的预约，取消成功，返回 true
//注：输出中的 null 表示此对应函数无输出（其中：C
//的构造函数有返回值，但是也是无需输出） 示例 2： 输入：
//["BookingSystem","addLab","addLab","addLab","bookTime","cancelBooking","addLab","bookTime","bookTime","cancelBooking"]
//[[],[2,8,17],[2,2,10],[2,17,30],[1,9,28],[1],[6,1,30],[13,8,27],[9,26,30],[10]]
//输出：[null,true,false,true,2,true,true,2,6,false]
//解释：
// BookingSystem obj = BookingSystem(); // 返回 null 表示无输出
// obj.addLab(2,8,17); // 返回 true
// obj.addLab(2,2,10); // 与已有开放时段重叠，返回 false
// obj.addLab(2,17,30); // 添加后开放时段为[8,30)，返回 true
// obj.bookTime(1,9,28); // 返回 2
// obj.cancelBooking(1); // 返回 true（时段释放可再被预约）
// obj.addLab(6,1,30); // 返回 true
// obj.bookTime(13,8,27); // 此时段可被预约的实验室编号为
// 2、6，但由于其中最早添加到系统的实验室为 2 号实验室，故返回 2
// obj.bookTime(9,26,30); // 由于实验室 2
// 的未预约时段为[27,30)，所以预约不上，只能预约到实验室 6，故返回 6
// obj.cancelBooking(10); // 不存在编号为 10 的预约记录，取消失败，返回 false
//注：输出中的 null 表示此对应函数无输出（其中：C
//的构造函数有返回值，但是也是无需输出） 提示： 2 <= addLab, bookTime,
// cancelBooking 累计操作数 <= 1000 0 <= recordId, labId <= 1000 1 <= startTime
// < endTime <= 100 1 <= fromTime < toTime <= 100 [time1, time2) 表示左闭右开
// 2.   题目分析
//题目理解：
//实现一个实验室管理系统，有三个接口：
// l  增加编号为 labId 的实验室，并同时增加开放时段
// l  预约实验室的某个时段
// l  取消之前的某个预约，使得预约的时段再次空闲
//注意点：
// 1)    实验室要先开放再预约
//即没有开放的时间段是不能预约的。
// 2)
// 同一个实验室，增加的两段时间如果相邻，那么在预约的时候可以合起来一起被预约，以示例2为例，如下图所示：
//实验室2虽然是通过两次添加的开放时间段，但是可以被bookTime(13,8,27)这个请求预约。
// 3) 若存在一个或多个该时段的实验室可被预约，则预约其中最早添加到系统的实验室
//即需要按添加实验室的先后顺序排序，挑选最早添加到系统的实验室。
//解题思路：
// 1)    设计建模
//理解需求之后，在动手编码之前，我们可以画一个设计草图：
//整个实验室预约系统，可以分解为两个子系统：实验室的管理和预约记录的管理；这两者并不是孤立的，而是存在关联关系。
// l  实验室的管理
//需要实现的功能有实验室的增加、开放时段的增加
//需要记录每个实验室添加到系统中的先后顺序，目的是在同一个预约请求匹配多个实验室的情况下能够找到最早添加的。
// l  预约记录的管理
// a)     预约时：找到满足条件的开放的实验室，并对这段时间段打上占用标记
//筛选：找到满足条件的开放的实验室（可能是多个）
//排序：找到最早开放的实验室
//将找到的实验室的预约时段记录下来、打上标记，这样取消预约的时候才知道如何取消（使得这段时间段重新空闲出来）。
// b) 取消时：根据recordId找到之前预约的实验室，并对之前占用的时间段打上空闲标记
//打标记常见的有两种实现方法，一种是直接修改实验室的开放时段的状态，另外一种是额外用一个表登记。
// 2)    实现关键点
// a)     方案一：打点标记法
//注意到开放时段数据规模没有超过100，所以可以用打点法来标记哪些时间点已经被预约了。
//为每一个实验室都开辟一个101个元素的数组空间，0表示未开放、1表示空闲、2表示被占用……
//通常需要三种状态：未开放，开放且空闲，开放被占用
//预约时，置上占用标记；取消预约时，置上空闲标记。
//注：通常总的计算量超过100万就不适合打点标记法，关于数据规模的估算可以参考【案例开放023】上机编程题之性能学习交流http://3ms.huawei.com/km/groups/3803117/blogs/details/9892189?l=zh-cn
// b)    方案二：区间合并法
//每个实验室可能有多个开放时间段（每一个时间段为一个区间），如果我们不进行区间合并，那么以示例2为例：实验室2就不满足obj.bookTime(13,8,27);
//区间合并有三种场景：
//对场景3的解释：在addLab接口中，当已经存在[1,3)、[5,8)两个时段后，再添加[3,5)时，最后得到的连续可被预约的区间是[1,8)
//从下面C++代码可以看到，三种场景可以简化为一种场景、用一个循环来处理。
// 3.   员工1-C代码:79行、最大圈复杂度5
//员工2-C++代码：91行、最大圈复杂度6
#include <algorithm>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
using namespace std;

#define DEBUG
#ifdef DEBUG
#define PF(...) printf(__VA_ARGS__)
#else
#define PF(...)
#endif

class BookingSystem {
 public:
  struct Node {
    int labId;
    vector<pair<int, int>> times;
    Node(int iLabId) : labId(iLabId) {}
  };
  vector<Node> mAdd;
  map<int, vector<int>> mBook;
  BookingSystem() {}
  int findLad(int labId) {
    for (int i = 0; i < mAdd.size(); ++i) {
      if (mAdd[i].labId == labId) {
        return i;
      }
    }
    return -1;
  }
  bool IsCross(pair<int, int> &p, int startTime, int endTime) {
    return !(p.first >= endTime || p.second <= startTime);
  }
  void merge(vector<pair<int, int>> &times) {
    sort(times.begin(), times.end(),
         [](pair<int, int> &p1, pair<int, int> &p2) {
           return p1.first <= p2.first;
         });
    for (auto iter = times.begin() + 1; iter != times.end();) {
      if (iter->first == (iter - 1)->second) {
        (iter - 1)->second = iter->second;
        times.erase(iter);
      } else {
        iter++;
      }
    }
  }
  bool AddLab(int labId, int startTime, int endTime) {
    int pos = findLad(labId);
    if (pos == -1) {
      Node lab(labId);
      lab.times.emplace_back(startTime, endTime);
      mAdd.push_back(lab);
      return true;
    } else {
      Node &lab = mAdd[pos];
      for (auto &p : lab.times) {
        if (IsCross(p, startTime, endTime)) {
          return false;
        }
      }
      lab.times.emplace_back(startTime, endTime);
      merge(lab.times);
      return true;
    }
  }
  bool InBooking(int labId, int fromTime, int toTime) {
    for (auto p : mBook) {
      if (p.second[0] == labId) {
        pair<int, int> tmp{p.second[1], p.second[2]};
        if (IsCross(tmp, fromTime, toTime)) {
          return true;
        }
      }
    }
    return false;
  }
  int BookTime(int recordId, int fromTime, int toTime) {
    for (auto lab : mAdd) {
      for (auto &p : lab.times) {
        // cout << "lab:" << lab.labId << ' ' << p.first << ' ' << p.second <<
        // endl; cout << "book:" << fromTime << ' ' << toTime << endl;
        if (p.first <= fromTime && p.second >= toTime &&
            !InBooking(lab.labId, fromTime, toTime)) {
          vector<int> book{lab.labId, fromTime, toTime};
          mBook[recordId] = book;
          return lab.labId;
        }
      }
    }
    return -1;
  }
  bool CancelBooking(int recordId) {
    for (auto p : mBook) {
      if (recordId == p.first) {
        mBook.erase(recordId);
        return true;
      }
    }
    return false;
  }
};
//该解法用的是区间合并法。
//结构体Node的一个实例表示一个实验室：
// l  vector<pair<int, int>>
// times;存储所有开放的时间段，每个时间段用一个pair表示，其中first=startTime，second=endTime
// map<int, vector<int>> mBook;记录所有的预约信息：key= recordId，value=
// vector<int>，其中： n  [0]=实验室编号 n  [1]=fromTime n  [2]=toTime
//区间合并是在函数merge内完成的（一次函数调用合并一个实验室的区间）：
//首先用sort函数将所有区间按照startTime升序排列，然后从前往后遍历，只要当前区间的startTime等于前一个区间的endTime，那么就开始合并：
// n  更新前一个区间的endTime为当前区间的endTime
// n  删除当前区间
//用一个循环就完成了三种场景的区间合并，非常巧妙；代码比较简练。
//当实验室数量比较大的时候，遍历mAdd这个vector的效率就不高，改用map/unordered_map来管理实验室会高效很多。
